class BitArray:
    def __init__(self):
        self._lst = []
        self._front = 0
        self._back = 0

    def __len__(self):
        return self._back - self._front

    def _normalize(self):
        if self._front>=8:
            self._front = self._front-8
            self._back = self._back-8
            self._lst.pop(0)
            #self._lst.remove(self._lst[0])
    
    def push_back(self, bit):
        i = self._back/8
        if i>=len(self._lst): self._lst.append(0)
        self._lst[i] = (self._lst[i]<<1) + bool(bit)
        self._back = self._back + 1
        
    def pop_front(self):
        res = self.front()
        self._front = self._front + 1
        self._normalize()
        return res

    def front(self):
        if self._back>8:
            shift = 8-self._front-1
        else:
            shift = len(self)-1
        if shift<0 or shift>7: raise IndexError('index out of range')
        return (self._lst[0]>>shift)&1

    def clean(self):
        self._lst = []
        self._front = 0
        self._back = 0
    
    def toString(self):
        s = str(self._front)+'\n'+str(self._back)+'\n'
        for x in self._lst:
            s = s + chr(x)
        return s

    def fromString(self, front, back, string):
        self._front = front
        self._back =  back
        self._lst = []
        for x in string:
             self._lst.append(ord(x))
